package Year22_Month06.day25;

public class 二叉搜索树中的删除操作 {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;//当前指针
        TreeNode parent = null;//记录上一个遍历的节点
        //找到待删除节点
        while(cur != null){
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                break;
            }
        }
        if(cur == null) return root;//如果说没有找到待删除的节点，那么就返回根节点就好（这里也包含了测试用例为[]的情况）
        if(cur.left == null){//1.左子树为空(可能为根节点) 同时处理
            if(parent == null){//这里添加这种情况的识别是因为待删除节点可能是根节点
                root = cur.right;
            }else{
                if(parent.left == cur) parent.left = cur.right;
                else parent.right = cur.right;
            }
            cur.right = null;
        }
        else if(cur.right == null){//2.右子树为空（可能为根节点）
            if(parent == null){//这里添加这种情况的识别是因为待删除节点可能是根节点
                root = cur.left;
            }else {
                if (parent.left == cur) parent.left = cur.left;
                else parent.right = cur.left;
            }
            cur.left = null;
        }
        else{//这就是最后一种情况了，就是当前节点的左右子树都在，这种的比较特殊，这里的删除要换一种形式
            //这种删除就是找一个合适的节点值进行覆盖
            parent = cur;
            TreeNode fac = cur.right;//这个节点用来找左子树的最大值或者说右子树的最小值
            //一般情况我们的选择就是右子树的最小值
            while(fac.left != null){
                parent = fac;
                fac = fac.left;
            }
            //找到后覆盖当前待删除节点
            cur.val = fac.val;
            if(parent.left == fac){//如果找到的节点是父节点的左子树
                parent.left  = fac.right;
            }else{//如果找到的节点为父节点的右子树
                parent.right = fac.right;
            }
        }
        return root;
    }
}
